跳到主要内容

剑指 Offer 47.礼物的最大价值

· 阅读需 3 分钟

1、题干​

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

 

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

 

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：dp[i][j]+=max(dp[i−1][j],dp[i][j−1])dp[i][j] += max(dp[i-1][j], dp[i][j-1])


3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

image.png


5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算


6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

  • 执行用时: 56 ms
  • 内存消耗: 44.1 MB